#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

from pprint import pprint


class PowerOf2Dict:
    def __init__(self, n=32):
        self.init(n)

    def init(self, n):
        self.dict = {}          # { digit : tuple() }

        for i in range(n):
            power_result = 1 << i     # HINT: 等同于 2^i / 2**i
            self.add_the_power(power_result)

    def add_the_power(self, power_result):
        s = str(power_result)         # input 1024 => "1024"
        sorted_s = tuple(sorted(s))      # "1024" => ('0', '1', '2', '4') , 排序, 简化out of order
        digit_num = len(s)

        if digit_num not in self.dict:
            self.dict[digit_num] = []

        self.dict[digit_num].append(sorted_s)

    def match(self, changeable_num):
        s = str(changeable_num)         # "1024"
        sorted_s = tuple(sorted(s))     # ('0', '1', '2', '4')
        digit_num = len(s)              # 4位
        zero_num = s.count('0')         # 有1个0

        # 1024有一个0, 所以要尝试匹配3位数, 4位数
        for try_digit_num in range(digit_num - zero_num, digit_num+1):
            try_pattern = sorted_s[-try_digit_num:]     # 如果只匹配3位数, 选择 ('0', '1', '2', '4')[-3:] 的后3位
            if self.match_specific_len(try_digit_num, try_pattern):
                return True

        return False

    def match_specific_len(self, digit_num, try_pattern):
        # print(digit_num, try_pattern)
        possible = self.dict.get(digit_num, [])
        # print(possible)

        for ele in possible:
            if ele == try_pattern:
                return True

        # digit_num 中的都没有匹配到
        return False


# global_p = PowerOf2Dict(64)
global_d = PowerOf2Dict(49)
# pprint(global_d.dict)


def test():
    # 1 2 4 8
    # 16 32 64
    # 128 256 512
    # 1024 2048 4096 8192
    # 16384 32768 65536
    # 131072 262144 524288
    # 1048576 2097152 4194304 8388608
    # 16777216 33554432 67108864
    # 134217728 268435456 536870912
    # 1073741824 2147483648

    for i in range(32):
        assert global_d.match(2**i) == True

    assert global_d.match(124) == False
    assert global_d.match(1024) == True
    assert global_d.match(10240) == True
    assert global_d.match(102400) == True
    assert global_d.match(1002400) == True
    assert global_d.match(10020400) == True
    assert global_d.match(655630) == True
    assert global_d.match(2**18) == True


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
